class Solution {
public:
    int trap(vector<int>& height) {
       int len =height.size();
       int i =0;
       stack<int> st;
       int sum = 0;
       int perv,index;
       int L,H;
       while(i<len)
       {
            while(!st.empty()&&height[i]>height[st.top()])
            {
                index = st.top();
                st.pop();
                if(st.empty()) break;
                perv = st.top();
                L= i-perv-1;
                H = min(height[i],height[perv]) - height[index];
                sum+=L*H;
            }
            st.push(i);
            i++;
       }
       return sum;
    }
};
